package org.hot100_1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class leetcode75 {
//    public List<Integer> partitionLabels(String s) {
//
//        //key为每个字母，value为字母最后一次出现的下标
//        Map<Character,Integer> map = new HashMap<>();
//
//        List<Integer> res=  new ArrayList<>();
//
//        for (int i = 0; i < s.length(); i++) {
//            map.put(s.charAt(i),i);
//        }
//
//        int start = 0;
//        int end =0;
//
//        for (int i = 0; i < s.length(); i++) {
//            //不断的更新end，直到在当前的end内没有其他的字母
//            end =Math.max(end,map.get(s.charAt(i)));
//
//            if (i==end){
//                res.add(end-start+1);
//                start=end+1;
//            }
//        }
//        return res;
//    }

    public List<Integer> partitionLabels(String s) {
        HashMap<Character,Integer> location = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            location.put(s.charAt(i),i);
        }
        List<Integer> res= new ArrayList<>();
        int start = 0;
        int end =0;

        for (int i = 0; i < s.length(); i++) {
            end=Math.max(end,location.get(s.charAt(i)));

            if (i==end){
                res.add(end-start+1);
                start=end+1;
            }
        }
        return res;
    }
}
